/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(head==nullptr) return head;
        Node* cur=head;
        //创建新的链表
        while(cur){
            Node* newNode=new Node(cur->val);
            newNode->next=cur->next;
            cur->next=newNode;
            cur=cur->next->next;
        }
        cur=head;
        //设置random指针
        while(cur){
            if(cur->random!=nullptr){
                cur->next->random=cur->random->next;
            }
            cur=cur->next->next;
        }
        cur=head->next;
        Node* ptr=head;
        Node* prev=head->next;
        //拆分成为两个链表并且保证链表的完整性
        while(cur->next){
            ptr->next=ptr->next->next;
            cur->next=cur->next->next;
            ptr=ptr->next;
            cur=cur->next;
        }
        ptr->next=nullptr;
        return prev;
    }
};








